One goal of a broadband packet network is to provide a flexible system capable of handling multipoint or broadcast connections in addition to point-to-point connections. A wide class of applications, such as teleconferencing, entertainment video, local area network (LAN) bridging and distributed data processing require multipoint connections. Thus, an important component of a broadband packet network is a packet switch capable of packet replication and switching. Such a packet switch is referred to herein as a multicast packet switch.
A multicast packet switch is usually a serial combination of a copy network which replicates incoming packets and a point-to-point switch which routes the packet copies generated in the copy network to particular destinations. The concern herein is primarily with copy networks.
One example of a copy network is disclosed in Huang, A. and Knauer, S., "Starlite: A Wideband Digital Switch" Proceedings of Globecom 84 121-125. The copy network in this system (which is known as the Starlite System) is receiver initiated. The inputs to the copy network are original source packets and empty packets generated by receivers. Thus, for example, if a total of four copies of a packet from a given source are required, the original source packet and three empty packets containing the same source address are provided at the inputs to the copy network.
The copy network of the Starlite System comprises a sorting network and a broadcast network. Both of these networks comprise regularly interconnected identical switching nodes which are self-routing (i.e. routing decisions are made based on information contained in the packet headers). Initially, the sorting network sorts the input packets according to source address. Thus, at the outputs of the sorting network, the original source packets and the associated empty packets with the same source address appear contiguously. The broadcast network then replicates the data in each source packet and inserts this data into the data fields of the associated empty packets.
In the Starlite copy network, the process of packet replication requires synchronization of the sources and receivers and requires an "empty packet setup procedure". These are the main drawbacks of the Starlite copy network. It would be difficult to implement the Starlite copy network as part of a broadband packet network wherein packets experience variable delays due to buffering, multiplexing and switching in a multi-hop connection.
Another example of a copy network is disclosed in U.S. patent application Ser. No. 773,380 entitled Broadcast Packet Switching Network and filed for Jonathan Turner on Sept. 6, 1985 now issued as U.S. Pat. No. 4,734,907 Mar. 29, 1988. The Turner copy network employs a self-routing banyan network formed from regularly interconnected identical switching nodes and a set of memories known as broadcast and group translators (BGT's). The header of an input broadcast packet contains two fields, a copy number (CN) indicating the required number of copies of the packet and a broadcast channel number (BCN) used by the broadcast and group translators. Packets are replicated in the banyan network using an algorithm which involves splitting the copy number evenly. Using the table lookup method, trunk number translation is performed by the broadcast and group translators when packet copies appear at the outputs of the banyan network. Then the packet copies are routed to the appropriate destinations by a succeeding routing network. Packet collisions cannot be avoided in the banyan network used to replicate packets in the Turner patent application, i.e. the banyan network disclosed in the above-identified patent application is blocking. This means that two packets may arrive at a particular node simultaneously and attempt to leave on the same output link at the same time. Thus, each node has a complex design including buffers to prevent packet loss. Because of the buffers, the latency (i.e. the packet propagation time in the network) varies from packet to packet. In addition, the carried load of this copy network depends in part on the total number of copies requested, but this information is unknown a priori to the network since packet replication is a divergent branching process. As a result, the performance of the Turner copy network may be difficult to predict and control.
In view of the above, it is an object of the present invention to provide a non-blocking self-routing copy network with constant packet latency.